package 算法知识;

public class KMP {
    /**
     * @param str 主串
     * @param sub 子串
     * @param pos 从子串的pos位置开始匹配
     * @return 找到子串在主串当中的下标
     */
    public static int kmp(String str,String sub,int pos){
        if(str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0) return -1;
        if(pos < 0 || pos >= lenStr) return -1;

        int[] next = new int[lenSub];
        getNext(sub, next);

        int i = pos; //遍历主串
        int j = 0; //遍历子串

        while (i < lenStr && j < lenSub){
            if(j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if(j >= lenSub){
            return i-j;
        }
        return -1;
    }

    private static void getNext(String sub, int[] next) {
        //第一二位置
        next[0] = -1;
        next[1] = 0;
        int i = 2;//主串  已经提前走了一步
        int k = 0;//子串
        //遍历子串
        for (; i < sub.length(); ++i) {
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k + 1;
                k++;
                i++;
            }else {
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(kmp("1234567890","234",0));
    }
}
